import java.util.Collections;
import java.util.PriorityQueue;

class MedianFinder {

    /**
     * 规定：
     *  left为大根堆，维护顺序数据流左边区域，大小为m
     *  right为小根堆，维护顺序数据流右边区域，大小为n
     *  m == n || m == n+1*/

    public static PriorityQueue<Integer> left;
    public static PriorityQueue<Integer> right;
    public static int m;
    public static int n;

    public MedianFinder() {
        /**
         * 初始化函数*/
        left = new PriorityQueue<>(Collections.reverseOrder());
        right = new PriorityQueue<>();
        m = n = 0;
    }
    
    public void addNum(int num) {
        /**
         * 添加元素*/
        if(m == n) {
            // -left必定不会为空
            if(m == 0 || num < left.peek() || (num == left.peek() && num <= right.peek())) {
                left.offer(num);
            } else {
                right.offer(num);
                left.offer(right.poll());
            }
            m++;
        } else if(m == n + 1) {
            if(num < left.peek()) {
                left.offer(num);
                right.offer(left.poll());
            } else {
                right.offer(num);
            }
            n++;
        }
    }
    
    public double findMedian() {
        /**
         * 找出中位数*/
        if(m == n) {
            // -此处需用2.0，否则整型除法会舍去小数
            return (double)((left.peek() + right.peek()) / 2.0);
        } else {
            return left.peek();
        }
    }
}